
#include <assert.h>

#include <algorithm>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <vector>

// ======================
// 超时
// ======================
// class Solution {
//  public:
//   int mySqrt(int x)
//   {
//     if (x == 0) { return 0; }
//     if (x == 1) { return 1; }

//     std::vector<int> vec;
//     for (int i = x / 2; i >= 1; --i) { vec.push_back(i); }

//     auto iter = std::find_if(vec.begin(), vec.end(),
//                              [x](const int &v) -> bool { return v * v <= x;
//                              });
//     assert(iter != vec.end());
//     return *iter;
//   }
// };

class Solution {
 public:
  int mySqrt(int x)
  {
    if (x == 0) { return 0; }
    if (x == 1) { return 1; }

    // 这里成为了性能瓶颈。

    // std::vector<int> vec;
    // for (int i = x / 2; i >= 1; --i) { vec.push_back(i); }

    long l = 1;
    long j = x / 2;
    long mid;
    while (l <= j)
    {
      mid = (l + j) / 2;
      if (mid * mid == x)
      {
        return mid;
      } else if (mid * mid < x)
      {
        l = mid + 1;
      } else if (mid * mid > x)
      {
        j = mid - 1;
      }
    }
    return j;
  }
};

int main(int argc, char *argv[])
{
  Solution s;
  std::cout << s.mySqrt(0);
  return 0;
}
